//题目:
// 给出一个单词数组 words ，其中每个单词都由小写英文字母组成。
// 如果我们可以 不改变其他字符的顺序 ，在wordA的任何地方添加恰好一个字母使其变成 wordB ，那么我们认为wordA是wordB的前身 。
// 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身
// 词链是单词[word_1,word_2,...,word_k]组成的序列，k>=1，其中word1是word2的前身，word2是word3的前身，依此类推。
// 一个单词通常是 k == 1 的 单词链 。
// 从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。

// 示例 1：
// 输入：words = ["a","b","ba","bca","bda","bdca"]
// 输出：4
// 解释：最长单词链之一为 ["a","ba","bda","bdca"]

// 示例 2:
// 输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
// 输出：5
// 解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

// 示例 3:
// 输入：words = ["abcd","dbqca"]
// 输出：1
// 解释：字链["abcd"]是最长的字链之一。
// ["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。
 
// 提示：
// 1 <= words.length <= 1000
// 1 <= words[i].length <= 16
// words[i] 仅由小写英文字母组成。
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
//代码
class Solution 
{
    struct compare
    {
        bool operator()(const string& s1,const string& s2)
        {
            return s1.size()<s2.size();
        }
    };
public:
    int longestStrChain(vector<string>& words) 
    {
        int n=words.size();
        sort(words.begin(),words.end(),compare());
        //1.创建dp表————dp[i]表示：以words[i]为结尾的单词链的最大长度
        vector<int> dp(n,1);
        //2.初始化————暂无
        //3.填表————动态转移方程:if(words[k]是words[i]的前身]) dp[i]=max(dp[i],dp[k]+1);
        int ret=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i-1;j>=0;j--)
                if(is_ok(words[j],words[i]))
                    dp[i]=max(dp[i],dp[j]+1);
            ret=max(ret,dp[i]);
        }
        //4.确定返回值
        return ret;
    }
    bool is_ok(const string& str1,const string& str2)
    {
        if(str2.size()-str1.size()!=1) return false;

        int i=0,j=0;
        while(i<str1.size() && j<str2.size())
        {
            if(str1[i]!=str2[j]) j++;
            else i++,j++;
        }
        return (i==str1.size() && (j==str2.size() || j==str2.size()-1))?true:false;
    }
};